package com.gitee.feizns.explore.data_structure.graph;

import com.gitee.feizns.explore.data_structure.graph.utils.Graph;

import java.util.HashMap;
import java.util.Map;

/**
 * @author feizns
 * @since 2020/4/28
 */
public class EulerLoop {

    public static void main(String[] args) {
        Graph<Integer> graph = new Graph<>();
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 0);
        System.out.println(graph.size());
        EulerLoop loop = new EulerLoop(graph);
        System.out.println(loop.hasEulerLoop());
    }

    private Graph graph;

    public EulerLoop(Graph graph) {
        this.graph = graph;
    }

    public boolean hasEulerLoop() {
        if ( count() == 1 ) {
            for (Object node : graph.nodes()) {
                if ( graph.adj(node).size() % 2 != 0 )
                    return false;
            }
            return true;
        }
        return false;
    }

    private int count() {
        Uf uf = new Uf();
        for (Object node : graph.nodes())
            uf.add(node);
        for (Object node : graph.nodes()) {
            for (Object o : graph.adj(node))
                uf.union(node, o);
        }
        return uf.size();
    }

    public static class Uf<K> {

        private Map<K, K> parents = new HashMap<>();

        private int size;

        public int size() {
            return size;
        }

        public void union(K s, K t) {
            K sp = find(s);
            K tp = find(t);
            if ( sp != tp ) {
                parents.put(sp, tp);
                size--;
            }
        }

        private K find(K k) {
            K v = parents.get(k);
            if ( v != null ) {
                if ( v != k )
                    parents.put(k, find(v));
            }
            return parents.get(k);
        }

        public void add(K k) {
            parents.put(k, k);
            size++;
        }

    }

}
